#include<iostream>
#include<vector>

// 定义二叉树的节点结构
struct TreeNode {
    int val;                // 节点值
    TreeNode *left;         // 左子节点
    TreeNode *right;        // 右子节点
    TreeNode() : val(0), left(nullptr), right(nullptr) {}           // 默认构造函数
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}      // 带有初始值的构造函数
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} // 完整构造函数
};

class Solution {
public:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> result;
        func(root, result);
        return result;
    }

    void func(TreeNode* cur, std::vector<int>& vec){
        if(cur == NULL) return;
        func(cur->left, vec);
        func(cur->right, vec);
        vec.push_back(cur->val);
    }
};

int main()
{
    // 创建示例二叉树： 1, null, 2, 3
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);

    Solution s;
    std::vector<int> result = s.postorderTraversal(root);

    // 输出结果
    for (int value : result) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}